package leetcode_day._2023._12;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 1671.得到山形数组的最少删除次数
 * 算法：贪心 + 动态规划
 * 枚举 [1 ... n - 2], 以当前位置为山脉,
 * 要算最少删除数, 反过来, 只要算出山脉左边的最长递增序列个数和右边的最长递减序列个数
 * 求最长递增序列, 两种做法, 一种时间复杂度 O(n ^ 2); 另一种时间复杂度 (nlogn), 空间复杂度 O(n)
 *
 * @author yezh
 * @date 2023/12/22 10:50
 */
public class _22 {

    // 时间复杂度 O(n ^ 2)
    public int minimumMountainRemovals_one(int[] nums) {
        int n = nums.length;
        // dp[i]: 到当前位置的最大上升序列个数
        int[] dp = new int[n], dp2 = new int[n];
        Arrays.fill(dp, 1);
        Arrays.fill(dp2, 1);
        for (int i = 1; i < n; i++)
            for (int j = 0; j < i; j++)
                if (nums[i] > nums[j]) dp[i] = Math.max(dp[i], dp[j] + 1);
        for (int i = n - 2; i >= 0; i--)
            for (int j = n - 1; j > i; j--)
                if (nums[i] > nums[j]) dp2[i] = Math.max(dp2[i], dp2[j] + 1);
        int res = Integer.MAX_VALUE;
        for (int i = 1; i < n - 1; i++) if (dp[i] > 1 && dp2[i] > 1) res = Math.min(res, n - dp[i] - dp2[i] + 1);
        return res == Integer.MAX_VALUE ? 0 : res;
    }

    public int minimumMountainRemovals(int[] nums) {
        int n = nums.length;
        int[] suf = new int[n];
        List<Integer> g = new ArrayList<>(n);
        for (int i = n - 1; i >= 0; i--) {
            int x = nums[i];
            // 找到最大的比 x 小的数
            int j = lowbound(g, x);
            if (j == g.size()) g.add(x);
            else g.set(j, x);
            suf[i] = j + 1;
        }
        int ans = 0;
        g.clear();
        for (int i = 0, pre, j; i < n; i++) {
            int x = nums[i];
            j = lowbound(g, x);
            if (j == g.size()) g.add(x);
            else g.set(j, x);
            pre = j + 1;
            if (pre > 1 && suf[i] > 1) ans = Math.max(ans, pre + suf[i] - 1);
        }
        return n - ans;
    }

    int lowbound(List<Integer> g, int target) {
        int l = 0, r = g.size() - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            // l - 1 永远指向小于 target 的数
            if (g.get(mid) < target) l = mid + 1;
                // r + 1 永远指向大于 target 的数
            else r = mid - 1;
        }
        return l;
    }

}
